package sort;

/**
 * HeapSort
 *
 * @author admin
 * @version 2023/11/02 11:20
 **/
public class HeapSort implements SortStrategy{
    @Override
    public void sort(int[] a) {
        for(int i=a.length/2-1;i>=0;i--)
        {
            heapify(a,a.length,i);
        }

        swap(0,a.length-1,a);
        int len=a.length;
        int j=1;
        for(int i=a.length-1;i>=1;i--)
        {
            heapify(a,i,i/2-1);
            swap(0,i-1,a);
        }
    }
    public void heapify(int[] a,int len,int cur)
    {
        if(cur<0) return;
        int leftChildIndex=2*cur+1;
        int rightChildIndex=2*cur+2;
        if(leftChildIndex>=len)
        {
            return;
        }
        int maxIndex=cur;
        int leftChild=Integer.MIN_VALUE;
        int rightChild=Integer.MIN_VALUE;
        if(leftChildIndex<len)
        {
            leftChild=a[leftChildIndex];
        }
        if(rightChildIndex<len)
        {
            rightChild=a[rightChildIndex];
        }
        if(leftChild>a[maxIndex])
        {
            maxIndex=leftChildIndex;
        }
        if(rightChild>a[maxIndex]){
            maxIndex=rightChildIndex;
        }
        if(maxIndex!=cur)
        {
            swap(maxIndex,cur,a);
            heapify(a,len,maxIndex);
        }
        heapify(a,len,maxIndex-1);

    }
}
